Such broadcasting has been done in accordance with a Digital Television Standard published in 1995 by the Advanced Television Systems Committee (ATSC) as Document A/53.
The component of the broadcast DTV signal to which the receiver synchronizes its operations is called the principal signal, and the principal signal is usually the signal received directly over the shortest transmission path. Therefore the multipath signal components of the broadcast TV signal received over other paths are usually delayed with respect to the principal signal and appear as lagging ghost signals. It is possible however, that the direct or shortest path signal is not the signal to which the receiver synchronizes. When the receiver synchronizes its operations to a (longer path) signal that is delayed respective to the direct signal, there will be a leading ghost signal caused by the direct signal, or there will a plurality of leading signals caused by the direct signal and other reflected signals of lesser delay than the signal to which the receiver synchronizes. In the DTV are ghost signals are customarily referred to as “echoes”, because of their similarity to echoes in transmission lines that are terminated other than with their characteristic impedance. The leading ghost signals are referred to as “pre-echoes”, and the lagging ghost signals are referred to as “post-echoes”. The ghost signals or echoes vary in number, amplitude and delay time from location to location and from channel to channel at a given location. Post-echoes with significant energy have been reported as being delayed from the reference signal by as many as sixty microseconds. Pre-echoes with significant energy have been reported leading the reference signal by as many as thirty microseconds. This 90-microsecond or so possible range of echoes is appreciably wider than television receiver designers generally supposed until midyear 2000.
The adaptive filtering used for channel equalization and echo cancellation in receivers for DTV signals broadcast in accordance with the ATSC standard has generally been a transversal filter the kernel of which is tapped at symbol intervals for implementing what is termed “synchronous equalization”. Synchronous equalization of real-only received signal is attempted, by adjusting the phase of received signal to minimize any imaginary component of the received signal. The attempt at adjustment is often made using decision-feedback methods based on the response of the adaptive filtering. If synchronous equalization is employed, the received signal is under-sampled when phase modulation of the received signal occurs during multipath reception, so rapidly changing phase modulation cannot be tracked by the adaptive filtering. Until midyear 2000, the range of echoes with appreciable energy was believed to extend from pre-echoes advanced by no more than three or four microseconds to post-echoes delayed as much as forty microseconds or so. Accordingly, the kernel of the adaptive filtering used for synchronous equalization of real-only received signal in most designs had only about 500 taps at symbol-epoch intervals.
It is known generally in digital communications receiver design that “fractional equalization”, in which the adaptive filtering kernel has taps at less-than-symbol-epoch intervals outperforms synchronous equalization when multipath reception conditions obtain. Page 535 of Data Communications Principles by Gitlin, Hayes & Weinstein, published in 1992 by Plenum Press of New York, indicates that a (¾)-symbol-epoch fractional equalizer performs substantially as well as the (½)-symbol-epoch fractional equalizer known without doubt to employ adequate sampling. Fractional equalization costs more in die area, of course, supposing the adaptive filtering to be constructed in a monolithic integrated circuit. A (¾)-symbol-epoch fractional equalizer has one-third more taps than a synchronous equalizer, or more than 640 taps. This appears to have deterred fractional equalization being used in DTV signal receivers designed for use in homes and made available for purchase before April 2001.
Training signals can be used for determining the weighting coefficients of adaptive filtering used for channel equalization and echo suppression in receivers for television signals. For example, a subcommittee of the ATSC approved ghost-cancellation reference (GCR) signals that incorporated Bessel chirp signals on pedestals in the 28th horizontal scan lines of image fields of analog television signals broadcast in accordance with a National Television System Committee (NTSC) standard used in the United States of America. The Bessel chirps in the later of the two image fields of each television frame are of opposite sense of polarity from the Bessel chirps in the earlier of the two image fields. This supports the receiver combining Bessel chirps from an even-numbered plurality of consecutive image fields to suppress pedestal, horizontal synchronizing pulse, color burst and porch information accompanying the Bessel chirps to generate a separated GCR signal together with the echoes, or ghosts, thereof. The separated GCR signal is employed as a training signal from which the weighting coefficients of adaptive filtering used for equalization and echo-suppression are determined. This determination is conveniently made by digitizing the GCR signal as separated from received NTSC analog television signal, determining the discrete Fourier transform (DFT) of successive samples of the digitized separated GCR signal and its ghosts as received off-the-air, and dividing that DFT term-by-corresponding term by the DFT of successive samples of a digitized ghost-free GCR signal as known a priori and stored in read-only memory at the receiver. The result of this term-by-term division is a DFT characterizing the actual reception channel as to its frequency response. This DFT is divided term-by-corresponding-term into a DFT characterizing the ideal reception channel as to its frequency response, to determine the DFT of the system function in the frequency domain of the adaptive filtering to be used for equalization and echo-suppression. This last DFT in the frequency domain is subjected to an inverse discrete Fourier transform (IDFT) procedure to generate the weighting coefficients of the adaptive filtering kernel in the time domain. These are closed-form computations of the weighting coefficients of adaptive filtering used for equalization and echo-suppression. A definite solution as to the value of each weighting coefficient in the filter kernel is directly obtained, without open-form computations for successively approximating that value with reduced error over time.
Fourier transforms in general and DFTs in particular are known to have an interesting property, which is not exploited in the adaptive filtering procedure described in the previous paragraph. A shift of the original data within the transform window is reflected solely in a change in the phasings of the transform coefficients and not in their amplitudes. This “Fourier transform shift theorem” was propounded by E. O. Brigham in “The Fast Fourier Transform” published in 1974 by Prentice-Hall of Englewood Cliffs, N.J. This property underlies fast computation of DFTs of continuous data streams by methods such as those described by K. B. Welles II and R. I. Hartley in their U.S. Pat. No. 4,972,358 issued 20 Nov. 1990 and titled “Computation of Discrete Fourier Transform Using Recursive Techniques”.
Blind-equalization methods have been resorted to for determining the weighting coefficients of adaptive filtering used for equalization and echo-suppression in receivers for ATSC digital television (DTV) signals, because the ATSC DTV signal does not provide a good training signal for procedures similar to those described in the preceding paragraph. The data field synchronizing (DFS) signals specified by ATSC Document A/53 each include a PN511 pseudo-random noise signal and a triple PN63 pseudo-random noise signal. At the time Document A/53 was published, these pseudo-random noise (PN) signals were envisioned as being used as training signals for adaptive channel-equalization and echo-suppression filtering. The design of the DFS signal does not avoid the PN signals being overlapped by the echoes of previous data in the DTV signal that have significant energy, however, nor does the design avoid some echoes of these PN signals that have significant energy overlapping subsequent data in the DTV signal. Consequently, even though the PN signals have auto-correlation functions that might suit them for match filtering, the DFS signals have not proven in actual practice to be satisfactory training signals for adaptive equalization and echo-suppression filtering, because echoes of the PN signals are not readily distinguishable from other data and their echoes.
Therefore, data-directed methods have been resorted to for computing on a continuing basis the weighting coefficients of the adaptive filtering used for equalization and echo-suppression in receivers for ATSC DTV signals. The approaches usually are auto-regressive spectral analyses, which are generally described as follows. The actual response of the adaptive filtering to received signal is data-sliced, or quantized, to generate an estimate of the symbols actually transmitted. The actual response of the adaptive filtering to received signal is compared symbol-epoch-by-symbol-epoch with the estimates of the symbols actually transmitted to generate an error signal to be used in a decision-feedback procedure for calculating the weighting coefficients of the adaptive filter. The decision-feedback procedure uses one of a variety of known algorithms that operate on a successive approximation basis.
LMS-gradient algorithms used in data-directed equalization methods are quite slow and are prone to stalling at local minima in the decision-feedback error signal, rather than continuing to the minimal decision-feedback error signal condition overall. Initialization of the adaptive filtering used for equalization and ghost cancellation normally takes a second or so after the reception channel is changed, which makes channel surfing difficult. Some receivers store weighting coefficients from the last time a channel was tuned to, to furnish a starting point for initializing the adaptive filtering.
LMS-gradient algorithms adapt slowly, so rapidly occurring changes in multipath conditions cannot be followed. This will at times lead to the weighting coefficients being completely erroneous for changed multipath condition, causing data slicing errors frequently enough that the error-correction capabilities of the system are overwhelmed. In some instances the multipath conditions do not return to a previous state which the weighting conditions are reasonably correct for, to cause data slicing errors to be infrequent enough that they can be corrected. Then, there is a second or so interval after rapid changes in multipath conditions pass before the LMS-gradient algorithm can re-initialize the weighting coefficients of the adaptive filtering. Continuously changing multipath conditions can cause a loss of tracking in which data slicing errors too frequent to be corrected persist over protracted intervals many seconds long.
Alternatively, recursive least squares (RLS) filter adaptation methods are the data-directed equalization methods used for computing the weighting coefficients the adaptive filtering a DTV receiver uses for equalization and ghost-cancellation. If signal-to-noise conditions are high, the RLS algorithm converges in about 2M+2 iterations for small error signals, where M+1 is the number of taps in the kernel of the adaptive filter, which is typically about an order of (binary) magnitude faster than LMS-gradient algorithms converge. Such faster convergence would appear to reduce the chances for loss of adaptive filter tracking owing to dynamic multipath conditions and for such loss being of protracted duration. However, the tracking performance is influenced not only by the rate of convergence (which is a transient characteristic) but also by fluctuation of the steady-state performance of the algorithm as influenced by measurement and algorithm noise. With both algorithms tuned to minimize the misadjustment of the filter response by a proper optimization of their forgetting rates, the LMS algorithm exhibits tracking performance superior to that of the RLS algorithm. Moreover, dynamic multipath conditions tend to be more troublesome during weak-signal reception where the convergence of the RLS algorithm is not so much greater than that of the LMS-gradient algorithm is not so much greater than that of the LMS-gradient algorithms.
RLS methods generally involve a computational cost that increases about as the square of the number of taps contained in the adaptive filter. This is a prohibitively high cost for a DTV receiver designed for use in homes. The fast transversal filters (FTF) algorithms realize the RLS solution with a computational cost that increases only linearly with the number of taps contained in the adaptive filter, as in the LMS-gradient algorithms. The computational cost of the FTF algorithms is at least four times larger than that for the LMS-gradient algorithms, however, with division calculations being required. For an adaptive filter having an (M+1)-tap kernel, the LMS-gradient algorithms require about 2M+1 multiplications and 2M additions/subtractions, with no divisions being required. The FTF algorithms require at least 7M+12 multiplications, 4 divisions, and 6M+3 additions/subtractions, with additional computation being required to avoid long-term instabilities.
Like the LMS-gradient algorithms, the FTF algorithms can suffer from stalling at local minima in the error signal, but methods are known for preventing such stalling. The more intractable problem with FTF algorithms is a potential explosive instability arising from word-length limitations in the weighting-coefficient computer causing accumulated rounding errors. One method that has been used for avoiding this explosive instability is to evaluate error signals developed by comparing the results of alternative ways of calculating the FTF algorithm, the differences in results being attributed to errors introduced by rounding off to accommodate word-length limitations in the weighting-coefficient computer. Such methods increase computational complexity by another 15% or so. Another method that has been used for avoiding this explosive instability is periodically starting the FTF algorithm, with an LMS-gradient algorithm taking over in the interim proceeding from the weighting coefficients the FTF algorithm has computed. The LMS-gradient algorithm eliminates accumulated errors in the coefficients, so the FTF algorithm can resume its calculations without accumulated round-off errors. The hand-off to the LMS-gradient algorithm also increases computational complexity.
The adaptive filters that have previously been used for equalization and echo-suppression in receivers for ATSC DTV signals are tracking filters that perform auto-regressive spectral analyses. When deep fading occurs suddenly during dynamic multipath reception conditions, there is a tendency for tracking to be lost. Tracking of the adaptive filtering may be impossible to recover unless a complete re-initialization of its weighting coefficients can be accomplished before there is another sudden change in dynamic multipath reception conditions. DTV receiver designers have attempted to solve the loss of tracking problem by improving the tracking rate of the adaptive filtering. This attempts to prevent loss of tracking, rather than dealing with the problem of re-initializing filter coefficients “instantly” when tracking is lost. The problem is that objects moving at fairly low velocity can at times interrupt reception from one of two reception paths of similar strength to cause tremendous changes in signal phase that are nearly “instantaneous”. Accordingly there will always be times, hopefully rare, when adaptive tracking of the adaptive filter will be lost. The question then circles back to how rapidly the adaptive filter coefficients can be re-initialized after tracking is lost, particularly when reception conditions do not change back to a previous state. A few seconds is simply too long, particularly since audio as well as video is lost.
Auto-regressive spectral analyses are handicapped in regard to how rapidly the weighting coefficients of the adaptive filtering can be re-initialized after tracking is lost. The ultimate limit on how rapidly re-initialization is possible after loss of tracking is determined by the desideratum that re-initialization of the weighting coefficients should be deferred until the data on which their computation is based no longer appreciably affect the adaptive filtering response. Such deferral is necessary in order to assure stability of the feedback loops in which error signal is derived from the adaptive filtering response to support computation of the weighting coefficients.
The speed of re-initialization is limited not only by the latency of the adaptive filtering used for equalization and echo-suppression, however, but additionally by the latency associated with computation of the weighting coefficients from the decision-feedback error signals. The updates of weighting coefficients are not computed in parallel in the auto-regressive methods, but are computed seriatim based on minimizing the decision-feedback error signals over time. The updates of the weighting coefficients can be applied to the adaptive filter serially as they are computed, but most designs avoid undesirable reverse-time effects by periodically applying the updates of the weighting coefficients to the adaptive filter so as to update the weighting coefficients in the entire kernel simultaneously in a technique known as “block updating”. The serial, rather than parallel, computation of updates for the weighting coefficients slows the adaptation of the filtering used for equalization and echo-suppression, particularly when block updating of the kernel weighting coefficients is done.
Furthermore, the auto-regressive methods employ open-form computation for continually adjusting the kernel weighting coefficients of the adaptive filtering using successive approximation techniques, rather than computing those weighting coefficients outright using closed-form computation. These open-form computations convolve the adaptive filter kernel with several blocks of signal samples, rather than a single block of samples. This tends to make initial computation of an (M+1)-tap kernel an operating method with steps some (3M+2) times N in number. This sort of operating method tends to take considerable time to perform, since these steps N(3M+2) in number have to be performed at the normal sampling rate through the adaptive filter
The factor (3M+2) arises from (2M+1) sample epochs being required for convolving (M+1) samples of input signal to the adaptive filter with the (M+1)-tap kernel to generate the (M+1) samples of decision-feedback signal required for updating all the weighting coefficients in the kernel, and from (2M+1) sample epochs being required for convolving the (M+1) samples of the decision-feedback signal gradient with the (M+1)-tap kernel to generate the updates of all the weighting coefficients in the kernel. The latter convolution procedure is presumed to commence next sample epoch after the first sample of decision-feedback signal is generated by the former convolution procedure, so the latter convolution procedure overlaps the former convolution procedure over M sample epochs.
The factor N is reciprocally related to an attenuation factor that is introduced into each successive one of the computation to update the weighting coefficients applied to a respective one of the kernel taps. The factor N is introduced into these computations so that the optimum value of each weighting coefficient is approached or reached through successive approximation. That is, the weighting coefficients are generated in the auto-regressive adaptive-filtering methods by long-term accumulations of decision-feedback error signal energy supplied in small increments and small decrements. These procedures result in lowpass recursive filtering of each weighting coefficient in the adaptive filtering kernel, which suppresses the effects of noise on the computation of the weighting coefficients. The noise comprises quantization noise generated in the digital portion of the receiver, Johnson noise from the analog portion of the receiver, impulse noise in the reception channel and possibly co-channel interference from NTSC analog television signals or from other ATSC DTV signals. This form of lowpass filtering of each weighting coefficient in the adaptive filtering kernel to suppress the effects of noise on its computation, which lowpass filtering is an integral part of the accumulation procedure that implements the computation, has a severe shortcoming as compared to lowpass filtering of each weighting coefficient and its updates after their generation. That is, since the weighting coefficients are computed seriatim in the auto-regressive adaptive-filtering methods, the number N of computations of each weighting coefficient that are averaged to arrive at the final value of that weighting coefficient actually employed in the adaptive filtering kernel appears as a multiplicative factor in determining the number of sample epochs required for completing initialization of the kernel weighting coefficients. If lowpass filtering of each weighting coefficient and its updates after their generation were used instead, the number N of computations of each weighting coefficient that are averaged to arrive at the final value of that weighting coefficient actually employed in the adaptive filtering kernel would simply add N sample epochs to the number of sample epochs required for completing initialization of the kernel weighting coefficients.
This specification discloses a novel equalization method for adapting the kernel weighting coefficients of the filtering used for equalization and echo-suppression in DTV signal receivers. This novel equalization method uses closed-form computation to obtain directly a complete update of the value of each weighting coefficient in the filter kernel, without open-form computations for successively approximating that value with reduced error over time. Closed-form computations that perform convolution of (M+1)-sample terms using discrete-Fourier-transform (DFT) procedures and convert the results obtained in the frequency domain back to the time domain using inverse-discrete-Fourier-transform (I-DFT) procedures can be performed in as few as 2(M+1) log2(M+1) sample epochs. The computations to determine the complete update of each weighting coefficient in the filter kernel are performed in parallel. After the complete updates are computed in parallel, all the weighting coefficients in the kernel of the adaptive filtering used for equalization and echo-suppression are simultaneously updated in full.
While the novel equalization method includes steps of lowpass filtering each weighting coefficient included in the adaptive filtering kernel, in order to suppress the effects of noise on the computation of the weighting coefficients, the lowpass filtering is performed after full updates of coefficient values have been computed. So, lowpass filtering of N successive values of each of the parallelly computed weighting coefficients adds only N sample epochs to the number of sample epochs required for completing initialization of the kernel weighting coefficients. N does not appear as a multiplicative factor in determining the number of sample epochs required for completing initialization of the kernel weighting coefficients.
Complete updating of the kernel weighting coefficients by the novel equalization method can initially be done in N+1(M+1) log2(M+1) sample epochs. During initialization or re-initialization N can be made to be zero, or to be otherwise smaller than it is during continuing operation thereafter.
N is usually an integral power of two, better to implement lowpass filtering that employs a tree of digital adders. Typical values are 32, 64, 128, or 256, with higher values of N being favored in auto-regressive adaptive filtering methods. U.S. patent application Ser. No. 60/193,301 indicates that (M+1) would preferably have a value at least 512 for representing a time period of 30–50 microseconds duration. That patent application further indicates that value of (M+1)=1024 would be preferred for a fractional equalizer using twice-baud-rate sampling and having its weighting coefficients adapted by the novel equalization method described in this specification. U.S. patent application Ser. No. 60/193,301 indicates that assured initialization or re-initialization takes about two milliseconds with preferred forms of the novel equalization method described in its specification, as compared to the 25-millisecond fastest initialization or re-initialization time claimed for auto-regressive blind-equalization methods. The novel equalization method described in U.S. patent application Ser. No. 60/193,301 and in this specification is never subject to the stalling problems that can afflict auto-regressive blind-equalization methods.
In order for DTV receiver designs employing a synchronous equalizer to accommodate the 90-microsecond-duration echo range that was publicly disclosed in 2000, (M+1) preferably has a value 2P where P is eleven or more. In order that a DTV receiver design employing a fractional equalizer using twice-baud-rate sampling can accommodate the 90-microsecond-duration echo range, (M+1) preferably has a value 2(P+1). Presuming that the duration of the window for the DFT is increased from a 47.6 microsecond duration to 190.3 microseconds, assured initialization or re-initialization will take another millisecond or so longer.